/* Author : 
 *    Daohang Shi 
 *    dshi7@wisc.edu 
 *    Fall  2013  
 *    */

#include <time.h>
#include <sys/time.h>
#include "CGRIP.h" 

Nodes nodes;
PNets pnets;
Route route;
Shapes shapes;
Box     box;
Pl pl;
Parser_cplex pcplex;
CGR cgr;
bool  debug_mode;

bool sortRanking1 (nodeRank i,nodeRank j) { return (i.rank<j.rank); }
void writePl(char *fileName);
void writeNode(char *fileName);

//  Define a Compare for the use of priority queue
class   CmpDist
{
  public:
    bool operator() ( pair<int,int> p1, pair<int,int> p2 )
    {
      return  p1.second < p2.second;
    }
};
bool  compare_pair_int_double2 ( const pair<int, double> &p1, const pair<int, double> &p2 ) { return  p1.second > p2.second; }

bool  compare_pair_int_int ( const pair<int, int> &p1, const pair<int, int> &p2 ) { return  p1.second > p2.second; }

int splitpath(char *path, char **dirpart, char **filepart) 
{ 
  static char        DOT[] = "."; 
  char       *dpart; 
  char       *fpart; 
  if ((fpart = strrchr(path, '/')) == NULL) 
  { 
    if ((dpart = strdup(DOT)) == NULL) 
      return -1; 
    if ((fpart = strdup(path)) == NULL) 
    { 
      free(dpart); 
      return -1; 
    } 
  } 
  else 
  { 
    if ((dpart = strdup(path)) == NULL) 
      return -1; 
    dpart[fpart - path] = '\0'; 
    if ((fpart = strdup(++fpart)) == NULL) 
    { 
      free(dpart); 
      return -1; 
    } 
  } 
  *dirpart = dpart; 
  *filepart = fpart; 
  return 0; 
} 

/*! \fn int CGP_readBenchmark(const char *fileName)
  \brief Read in the benchmark files and initialize the CGRIP. Note, you will not be running the CGRIP yet. 

  \param inAuxFile The benchmark name to read in.
  \returns 1 if successful, 0 otherswise(e.g. the input file is not valid) 
  */
int CGP_readBenchmark(const char *inAuxFile)
{
  char* dirpart = 0; 
  char* filepart = 0; 
  char pathName[1024];
  strcpy(pathName, inAuxFile);
  splitpath(pathName, &dirpart, &filepart);

  Auxf auxf;

  string fName = dirpart;
  fName += "/";
  fName += filepart;
  string auxFile = fName;
  cout<<"\nreading "<<auxFile<<endl;
  auxf.parse(dirpart, auxFile);

  cout<<"\nreading "<<auxf.nodes_file<<endl;
  nodes.parse(auxf.nodes_file);

  cout<<"\n\nreading "<<auxf.nets_file<<endl;
  pnets.parse(auxf.nets_file);

  cout<<"\nreading "<<auxf.shapes_file<<endl;
  shapes.parse(auxf.shapes_file);

  cout<<"\nreading"<<auxf.route_file<<endl;
  route.parse(auxf.route_file);

  return 1;

}

/*! \fn int CGP_readPlacement(const char *inPlFile)
  \brief Read in the placement file and initialize the coordinates.

  \param inAuxFile The benchmark name to read in.
  \returns 1 if successful, 0 otherswise(e.g. the input file is not valid) 
  */
int CGP_readPlacement(const char *inPlFile)
{
  string pl_file = inPlFile;
  cout<<"\nreading "<<pl_file<<endl;
  pl.parse(pl_file);
  return 1;
}

/*! \fn int CGP_setNodeCoordinate(const char *nodeName, const int llx, const int lly)
  \brief Set the coordinates of a moveable object.

  \param nodeName The name of the object to set the coordinates.
  \param llx The lower left x coordinate.
  \param lly The lower left y coordinate.
  \returns 1 if successful, 0 otherswise(e.g. the input name or coordinates are not valid) 
  */
int CGP_setNodeCoordinate(const char *nodeName, const int llx, const int lly)
{
  Node *node;
  NODE_ITERATOR it;

  node = new Node();
  node->name = nodeName;
  it = nodes.nodes.find(node);
  if(it==nodes.nodes.end())
    it = nodes.terminals.find(node);
  if(it==nodes.terminals.end()){
    cerr<<"Not found Node"<<nodeName<<endl;
    return 0;
  }
  delete node;
  node = *it;
  node->ll_xcoord=llx;
  node->ll_ycoord=lly;

  return 1;
}

void    CGR::genInitialGrid () 
{
  cout << "Start : Build Grid" << endl;

  //
  //
  /* to test whether solutions make sense */
  //  mj.clear(); mj.push_back (1); bj.clear(); bj.push_back(0);

  jsize = mj.size();

  /* Define some fundamental parameters in global grid */
  numLayers = route.numLayer;
  fullGridX = route.gridX;
  fullGridY = route.gridY;
  minX = route.llx;
  minY = route.lly;
  tileWidth = route.tileWidth;
  tileHeight = route.tileHeight;
  halfWidth = static_cast<uint32_t>(trunc(0.5*tileWidth));
  halfHeight = static_cast<uint32_t>(trunc(0.5*tileHeight));
  edgeCount2D = fullGridX*(fullGridY-1) + fullGridY*(fullGridX-1);
  edgeCount3D = numLayers * edgeCount2D + (numLayers-1) * fullGridX * fullGridY;
  vertCaps.clear();
  mws.clear();
  horizCaps.clear();
  mss.clear();
  viaSpacings.clear();
  for(uint32_t i = 0; i < numLayers; ++i) {
    vertCaps.push_back(route.vCap[i]);
    horizCaps.push_back(route.hCap[i]);
    mws.push_back(route.mWireWidth[i]);
    mss.push_back(route.mWireSpace[i]);
    viaSpacings.push_back(1);
  }
  cout << "FullGridX = " << fullGridX << endl;
  cout << "FullGridY = " << fullGridY << endl;
  cout << "numLayers = " << numLayers << endl;

  int ind = 0;
  //  store in cgr.V
  for ( int k=0; k<numLayers; k++ )
    for ( int j=0; j < fullGridY; j++ )
      for ( int i=0; i < fullGridX; i++ )
      {
        NetTerminal v;
        v.id = xyzToGridNetTerminalId( i,j,k ); 
        v.x = i;    v.y = j;    v.z = k;
        if ( ind != v.id )
          cout << ind << " " << v.id << " : " << v.x <<" "<<v.y<<" "<<v.z << endl;
        assert ( ind == v.id );
        ind ++;

        v.ne[0] = (i+1 <= fullGridX-1 )? return_edge_id ( i,j,k, 0 ):-1;
        v.nv[0] = (i+1 <= fullGridX-1 )? xyzToGridNetTerminalId( i+1,j,k ) : -1; 

        v.ne[1] = (i-1 >=0 )? return_edge_id ( i-1,j,k,0 ):-1;
        v.nv[1] = (i-1 >=0 )? xyzToGridNetTerminalId( i-1,j,k ) : -1; 

        v.ne[2] = (j+1 <= fullGridY-1 ) ? return_edge_id ( i,j,k,1 ):-1;
        v.nv[2] = (j+1 <= fullGridY-1 ) ? xyzToGridNetTerminalId( i,j+1,k ) : -1; 

        v.ne[3] = (j-1>=0 ) ? return_edge_id ( i,j-1,k,1 ):-1;
        v.nv[3] = (j-1>=0 ) ? xyzToGridNetTerminalId( i,j-1,k ) : -1; 

        v.ne[4] = (k+1 <= numLayers-1 )? return_edge_id ( i,j,k,2 ):-1;
        v.nv[4] = (k+1 <= numLayers-1 )? xyzToGridNetTerminalId( i,j,k+1 ) : -1; 

        v.ne[5] = (k-1 >=0 ) ? return_edge_id ( i,j,k-1,2 ):-1;
        v.nv[5] = (k-1 >=0 ) ? xyzToGridNetTerminalId( i,j,k-1 ) : -1; 

        V.push_back ( v );
      }
  ind = 0;
  //  store in cgr.E
  for ( int k = 0; k < numLayers; k++ )   {
    for ( int j=0; j< fullGridY; j++ )
      for ( int i=0; i< fullGridX-1; i++ )    {
        GridEdge    e;
        e.id = return_edge_id ( i,j,k,0 );
        assert ( e.id == E.size() );
        assert ( ind==e.id );
        ind++;
        e.srcPoint = xyzToGridNetTerminalId( i,j,k ); 
        e.snkPoint = xyzToGridNetTerminalId( i+1,j,k ); 
        e.cap = horizCaps[k]/(mws[k]+mss[k]);
        e.blk = 0;
        e.type = "HORIZ";
        e.util = 0;
        E.push_back ( e );
      }
    for ( int i=0; i<fullGridX; i++ )  
      for ( int j=0; j< fullGridY-1; j++ ) {
        GridEdge    e;
        e.id = return_edge_id ( i,j,k,1 );
        assert ( e.id == E.size() );
        assert ( ind==e.id );
        ind++;
        e.srcPoint = xyzToGridNetTerminalId( i,j,k ); 
        e.snkPoint = xyzToGridNetTerminalId( i,j+1,k ); 
        e.cap = vertCaps[k]/(mws[k]+mss[k]);
        e.blk = 0;
        e.type = "VERT";
        e.util = 0;
        E.push_back ( e );
      }
  }
  for ( int j=0; j < fullGridY; j++ )
    for ( int i=0; i< fullGridX; i++ )  
      for ( int k = 0; k < numLayers-1; k++ ) {
        GridEdge    e;
        e.id = return_edge_id ( i,j,k,2 );
        assert ( e.id == E.size() );
        assert ( ind ==e.id );
        ind++;
        e.srcPoint = xyzToGridNetTerminalId( i,j,k ); 
        e.snkPoint = xyzToGridNetTerminalId( i,j,k+1 ); 
        e.cap = 100000;
        e.blk = 0;
        e.type = "VIA";
        e.util = 0;
        E.push_back ( e );
        //  VIAS HAS UNFINITELY LARGE CAP
      }
  bool  consider_blockage = true;
  if ( consider_blockage == true ) {
    int capChanges = route.blockages.size();
    for(int i = 0; i < capChanges; ++i) {
      int gridCol1, gridRow1, layer1, gridCol2, gridRow2, layer2;
      double  blocked_ratio;
      gridCol1 = route.blockages[i].p1.x;
      gridRow1 = route.blockages[i].p1.y;
      layer1 = route.blockages[i].p1.z;
      gridCol2 = route.blockages[i].p2.x;
      gridRow2 = route.blockages[i].p2.y;
      layer2 = route.blockages[i].p2.z;
      blocked_ratio = route.blockages[i].blocked_ratio;
      assert(layer1 == layer2);
      if(gridCol1 == gridCol2) {
        // vert segment
        assert(gridRow1 == gridRow2+1 || gridRow1+1 == gridRow2);
        int edge_id = V[xyzToGridNetTerminalId(gridCol1, min(gridRow1, gridRow2), layer1-1)].ne[2];
        if ( edge_id != -1 )
          E[edge_id].blk += ceil(blocked_ratio*E[edge_id].cap); 
      }
      else if(gridRow1 == gridRow2) {
        // horiz segment
        assert(gridCol1 == gridCol2+1 || gridCol1+1 == gridCol2);
        int edge_id = V[xyzToGridNetTerminalId(gridCol1, min(gridRow1, gridRow2), layer1-1)].ne[0];
        if ( edge_id != -1 )
          E[edge_id].blk += ceil(blocked_ratio*E[edge_id].cap); 
      }
      else {
        cout << "Bad cap change" << endl;
        exit(0);
      }
    }
    //  check that blk will never overflow capacity
    for ( vector<GridEdge>::iterator itr = E.begin(); itr!= E.end(); itr++ ) 
      if ( (*itr).blk > (*itr).cap )
        (*itr).blk = (*itr).cap; 
  }

  cout << "E.size()=" << E.size() << endl;
  cout << "V.size()=" << V.size() << endl;
  cout << "Finish : Build Grid" << endl;
}

void    CGR::readRouting (const char *inGRFile) 
{
  cout << "Start : Read Routing" << endl;
  ifstream    infile;
  infile.open ( inGRFile );
  assert ( infile.is_open()==true );

  char    line[1024];
  char    name[256];
  int     net_id;
  int     seg_num;
  while ( infile.getline ( line, 1024 ) ) {
    if ( line[0] == 'n' ) {
      sscanf ( line, "%s %d %d", name, &net_id, &seg_num );
      CoarseNet   net ;
      net.old_index = net_id;
      int NUM = pnets.nets[net_id]->points.size();
      for ( int j =0; j < NUM; j++ ) {
        point   &pnet_point = pnets.nets[net_id]->points[j];
        NetTerminal t;
        t.x = (int)floor ( ( pnet_point.x - route.llx ) / route.tileWidth );  
        t.y = (int)floor ( ( pnet_point.y - route.lly ) / route.tileHeight );
        t.z = pnet_point.z - 1;
        net.terminal_pins.insert ( xyzToGridNetTerminalId ( t.x, t.y, t.z ) );
      }

      for ( int i=0; i<seg_num; i++ ) {
        infile.getline ( line, 1024 );
        int x1,y1,z1,x2,y2,z2;
        sscanf ( line, "(%d,%d,%d)-(%d,%d,%d)", &x1,&y1,&z1,&x2,&y2,&z2 );
        x1 = x1 / tileWidth;
        x2 = x2 / tileWidth;
        y1 = y1 / tileHeight;
        y2 = y2 / tileHeight;
        z1 --;  z2 --;
        Segment seg; 
        seg.s = xyzToGridNetTerminalId(x1,y1,z1); 
        seg.t = xyzToGridNetTerminalId(x2,y2,z2); 
        if ( x1 != x2 )
          seg.type = "HORIZ";
        if ( y1 != y2 )
          seg.type = "VERT";
        if ( z1 != z2 )
          seg.type = "VIA";

        net.sg.push_back ( seg );
        //
        vector<int> edge_vector = getEdgeVectorFromSegment ( seg );
        for ( vector<int>::iterator it = edge_vector.begin(); it!= edge_vector.end(); it++ ) {
          E[*it].nets_passing_through.insert ( nets.size() );
          net.edges.insert ( *it );
        }
      }
      infile.getline ( line, 1024 );
      map_from_net_old_index_to_idnex_in_nets.insert ( make_pair(net.old_index, nets.size()) );
      nets.push_back ( net );
    }
  }
  cout << "Number of nets : " << nets.size() << endl;
  cout << "Finish : Reading Routing" << endl;
}

void  CGR::getTotalOverFlow ( void ) 
{
  /* compute edge utilization */
  total_overflow = 0;
  for ( size_t i = 0; i< E.size(); i++ )
    E[i].util = 0;
  for ( int i =0; i< nets.size(); i++ ) 
    for ( set<int>::iterator it = nets[i].edges.begin(); it != nets[i].edges.end(); it++ )
      E[*it].util++;

  /* compute oveflow and congestion ratio */
  for ( size_t i = 0; i< E.size(); i++ ) {
    assert ( E[i].util == E[i].nets_passing_through.size() );
    total_overflow += (E[i].util+E[i].blk>E[i].cap)?(E[i].util+E[i].blk-E[i].cap):0 ;
    E[i].congestion_ratio = (double) ((E[i].blk + E[i].util)/(E[i].cap+0.0001));
  }
  cout << total_overflow << endl;
}

int CGP_runRouting(char *inGRFile, int time_budget, std::ofstream &stream_file ) 
{
  int status;
  cgr.init( );
  cgr.TCR = 1;

  //
  if ( true ) {
    double  k1 = 0;
    double  k2 = 1;
    double  k3 = 10;
    double  k4 = 10;
    cgr.tcr1 = 0.95;
    cgr.tcr2 = 1;
    cgr.tcr3 = 1.1;

    cgr.mj.clear(); cgr.bj.clear();
    //
    cgr.mj.push_back ( k1 );
    cgr.bj.push_back ( 0 );
    //
    cgr.mj.push_back ( k2 );
    cgr.bj.push_back ( (k1-k2)*cgr.tcr1 );
    //
    cgr.mj.push_back ( k3 );
    cgr.bj.push_back ( (k1-k2)*cgr.tcr1 + (k2-k3)*cgr.tcr2 );
    //  
    cgr.mj.push_back ( k4 );
    cgr.bj.push_back ( (k1-k2)*cgr.tcr1 + (k2-k3)*cgr.tcr2 + (k3-k4)*cgr.tcr3 );

    cgr.jsize = cgr.mj.size();
    for ( size_t j=0; j < cgr.jsize; j++ )
      stream_file << j << " : " << cgr.mj[j] << " " << cgr.bj[j] << endl;
  }

  cgr.genInitialGrid ();

  cgr.readRouting (inGRFile);

  bool  check_cgrip = false;

  cgr.getTotalOverFlow ();

  cgr.getTop20 ();

  if ( check_cgrip == true ) {
    cgr.getInputGlobalRoutingInfo ( stream_file );
    exit(0);
  }

  status = runMode8 ( (double)time_budget, stream_file );

  return 1;
}

int main(int argc, char **argv)  
{
  if(argc<5){
    cout << "Usage : ./IGRIP.exe <circuit.aux> <placement.pl> <routing.txt> <data.txt> <time budget>"<<endl;
    exit(1);
  }

  ofstream  stream_file;
  stream_file.open ( argv[4] );
  int time_budget = atoi(argv[5]);
  assert ( stream_file.is_open() );

  char *outputfile = NULL;
  bool writeOutFlag = false;
  //
  // read input files
  if(CGP_readBenchmark(argv[1])==0){
    cout<<"Error happened while reading the input files\n";
    exit(1);
  }
  //
  // read coordinates from a file
  if(CGP_readPlacement(argv[2])==0){
    cout<<"Error happened while reading placement info\n";
    exit(1);
  }
  route.extractBlockages_3();
  pnets.setCoordinates();
  //
  // run CGRIP and route the nets(time out:900s)
  if(CGP_runRouting( argv[3], time_budget, stream_file )==0){
    cout<<"Error happened while routing the nets\n";
    exit(1);
  }

  cout << "Program finishes!" << endl;

  return 0;
}

void  fixOneBox2 ( GridBox &b, std::ofstream &stream_file )
{
  //  start time
  int status;
  struct  timeval t1;
  gettimeofday ( &t1, NULL );

  cgr.buildGridinBox ( b );

//  cgr.getHist( stream_file );
  //  update mj and bj

  double  p1 = 0;
  double  p2 = 0;
  double  p3 = 0;
  int n1 = 0;
  int n2 = 0;
  int n3 = 0;

  stream_file << cgr.tcr1 << " " << cgr.tcr2 << endl;

  for ( size_t i=0; i<cgr.E_id.size(); i++ )
  {
    if ( cgr.E[cgr.E_id[i]].cap == 0 || cgr.E[cgr.E_id[i]].type == "VIA" )
      continue;
    if ( cgr.E[cgr.E_id[i]].congestion_ratio < cgr.tcr1 ) {
      p1 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n1++;
    }
    else  if ( cgr.E[cgr.E_id[i]].congestion_ratio< cgr.tcr2 ) {
      p2 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n2++;
    }
    else {
      p3 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n3++;
    }
  }

  cgr.getInputGlobalRoutingInfoInBox ( stream_file );

  //  before
  cgr.computeBoxObjVal();
  double  obj_before = cgr.obj_bad;
  //
  cgr.getCongestedNets ( stream_file ) ;

  cout << cgr.considered_nets.size() << endl;

  cgr.bnets.clear();

  //  solve ILP to obtain initial dual solution
  cgr.genModifiedNetsInBox5 (b); 

  //  initialize the edge weight with edge congestion ratio
  for ( vector<int>::iterator itr = cgr.E_id.begin(); itr!= cgr.E_id.end(); itr++ )
    cgr.E[*itr].weight = cgr.E[*itr].congestion_ratio;

  for ( size_t i=0; i< cgr.bnets.size(); i++ )  {
    CoarseNet &bnet = cgr.bnets[i];
    bnet.edges_backup = bnet.edges;
  }

  int iteration_number = 0;

  double  prev_objval = obj_before;
  double  curr_objval;
  while ( iteration_number < 20 ) {

    cout << "ready for next iteration" << endl;
    cgr.readyForNextIteration4 ( b );
    cout << "here" << endl;

    status = pcplex.getCplex();
    status = pcplex.CreateLargeILP3 ( stream_file );
    ++ iteration_number ;

    curr_objval = cgr.getObjValInBox();
    if ( curr_objval > prev_objval ) {
      break;
    }
    prev_objval = curr_objval;
  }

  cgr.refreshNetSegments ();

  //  after
  cgr.computeBoxObjVal();
  double  obj_after = cgr.obj_bad;
  //  stream_file << "AFTER : OBJ_IN_BOX = " << cgr.obj_bad << endl;
  //
  if ( obj_after > obj_before )
  {
    stream_file << "RECOVER " << endl;
    cgr.recoverNets ();
    cgr.computeBoxObjVal();
    obj_after = cgr.obj_bad;
    //    stream_file << "AFTER : OBJ_IN_BOX = " << cgr.obj_bad << endl;
  }
  //

  for ( vector<CoarseNet>::iterator itr_bnet = cgr.bnets.begin(); itr_bnet != cgr.bnets.end(); itr_bnet++ )  {
    bool isLegal = cgr.isLegalRoute ( cgr.nets[(*itr_bnet).old_index] );
    if ( cgr.isLegalRoute ( cgr.nets[(*itr_bnet).old_index] )==false) {
      cgr.printNet ( cgr.nets[(*itr_bnet).old_index] );
      exit(0);
    }
  }


  stream_file << "iteration number = " << iteration_number << endl;

  struct  timeval t2;
  gettimeofday ( &t2, NULL );
  double dt = (t2.tv_sec-t1.tv_sec)*1000000 + (t2.tv_usec-t1.tv_usec);
  stream_file << "runtime = " << dt/1000000<< endl;
  cgr.getInputGlobalRoutingInfoInBox ( stream_file );
  cgr.getInputGlobalRoutingInfo ( stream_file );

}

void  fixOneBox3 ( GridBox &b, std::ofstream &stream_file )
{
  //  start time
  int status;
  struct  timeval t1;
  gettimeofday ( &t1, NULL );

  cgr.buildGridinBox ( b );

  cgr.getHist( stream_file );
  //  update mj and bj

  double  p1 = 0;
  double  p2 = 0;
  double  p3 = 0;
  double  p4 = 0;
  int n1 = 0;
  int n2 = 0;
  int n3 = 0;
  int n4 = 0;

  stream_file << cgr.tcr1 << " " << cgr.tcr2 << endl;

  for ( size_t i=0; i<cgr.E_id.size(); i++ )
  {
    if ( cgr.E[cgr.E_id[i]].cap == 0 || cgr.E[cgr.E_id[i]].type == "VIA" )
      continue;
    if ( cgr.E[cgr.E_id[i]].congestion_ratio < cgr.tcr1 ) {
      p1 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n1++;
    }
    else  if ( cgr.E[cgr.E_id[i]].congestion_ratio< cgr.tcr2 ) {
      p2 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n2++;
    }
    else  if ( cgr.E[cgr.E_id[i]].congestion_ratio< cgr.tcr3 ) {
      p3 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n3++;
    }
    else {
      p4 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n4++;
    }
  }
  stream_file << "Discrete distribution : " << endl;
  stream_file << n1 << " " << n2 << " " << n3 << " " << n4 << endl;
  stream_file << p1/(p1+p2+p3+p4) << " "; 
  stream_file << p2/(p1+p2+p3+p4) << " "; 
  stream_file << p3/(p1+p2+p3+p4) << " "; 
  stream_file << p4/(p1+p2+p3+p4) << endl;

  cgr.getInputGlobalRoutingInfoInBox ( stream_file );

//  cgr.bdr1 = cgr.getACEInBox ( 0.6 );
//  cgr.bdr2 = cgr.getACEInBox ( 0.3 );
//  cgr.bdr3 = cgr.getACEInBox ( 0.2 );
  cgr.bdr1 = 0.6;
  cgr.bdr2 = 0.999995;
  cgr.bdr3 = 1.2;
  stream_file << "## New boundaries " << endl;
  stream_file << cgr.bdr1 << " " << cgr.bdr2 << " " << cgr.bdr3 << endl;
  cout << "## New boundaries " << endl;
  cout << cgr.bdr1 << " " << cgr.bdr2 << " " << cgr.bdr3 << endl;

  //  before
  cgr.computeBoxObjVal();
  double  obj_before = cgr.obj_bad;
  //
  cgr.getCongestedNets ( stream_file ) ;

  cout << cgr.considered_nets.size() << endl;

  cgr.bnets.clear();

  //  solve ILP to obtain initial dual solution
  cgr.genModifiedNetsInBox5 (b); 

  //  initialize the edge weight with edge congestion ratio
  for ( vector<int>::iterator itr = cgr.E_id.begin(); itr!= cgr.E_id.end(); itr++ )
    cgr.E[*itr].weight = cgr.E[*itr].congestion_ratio;

  for ( size_t i=0; i< cgr.bnets.size(); i++ )  {
    CoarseNet &bnet = cgr.bnets[i];
    bnet.edges_backup = bnet.edges;
  }

  int iteration_number = 0;

  double  prev_objval = obj_before;
  double  curr_objval;
  while ( iteration_number < 10 ) {

    cout << "ready for next iteration" << endl;
    cgr.readyForNextIteration4 ( b );
    cout << "here" << endl;

    status = pcplex.getCplex();
    status = pcplex.CreateLargeILP3 ( stream_file );
    ++ iteration_number ;

    curr_objval = cgr.getObjValInBox();
    if ( curr_objval > prev_objval ) {
      break;
    }
    prev_objval = curr_objval;
  }

  cgr.refreshNetSegments ();

  //  after
  cgr.computeBoxObjVal();
  double  obj_after = cgr.obj_bad;
  //
  if ( obj_after > obj_before )
  {
    stream_file << "RECOVER " << endl;
    cgr.recoverNets ();
    cgr.computeBoxObjVal();
    obj_after = cgr.obj_bad;
  }
  //

  n1 = n2 = n3 = n4 = 0;
  p1 = p2 = p3 = p4 = 0;
  for ( size_t i=0; i<cgr.E_id.size(); i++ ) {
    if ( cgr.E[cgr.E_id[i]].cap == 0 || cgr.E[cgr.E_id[i]].type == "VIA" )
      continue;
    if ( cgr.E[cgr.E_id[i]].congestion_ratio < cgr.tcr1 ) {
      p1 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n1++;
    }
    else  if ( cgr.E[cgr.E_id[i]].congestion_ratio< cgr.tcr2 ) {
      p2 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n2++;
    }
    else  if ( cgr.E[cgr.E_id[i]].congestion_ratio< cgr.tcr3 ) {
      p3 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n3++;
    }
    else {
      p4 += cgr.getEdgePenalty ( cgr.E_id[i] );
      n4++;
    }
  }

  stream_file << "Discrete distribution : " << endl;
  stream_file << n1 << " " << n2 << " " << n3 << " " << n4 << endl;
  stream_file << p1/(p1+p2+p3+p4) << " "; 
  stream_file << p2/(p1+p2+p3+p4) << " "; 
  stream_file << p3/(p1+p2+p3+p4) << " "; 
  stream_file << p4/(p1+p2+p3+p4) << endl;

  cout << "checking legality" << endl;
  for ( vector<CoarseNet>::iterator itr_bnet = cgr.bnets.begin(); itr_bnet != cgr.bnets.end(); itr_bnet++ )  {
    bool isLegal = cgr.isLegalRoute ( cgr.nets[(*itr_bnet).old_index] );
    if ( cgr.isLegalRoute ( cgr.nets[(*itr_bnet).old_index] )==false) {
      cgr.printNet ( cgr.nets[(*itr_bnet).old_index] );
      exit(0);
    }
  }
  cout << "finish checking legality" << endl;


  stream_file << "iteration number = " << iteration_number << endl;
  cgr.getHist( stream_file );

  struct  timeval t2;
  gettimeofday ( &t2, NULL );
  double dt = (t2.tv_sec-t1.tv_sec)*1000000 + (t2.tv_usec-t1.tv_usec);
  stream_file << "runtime = " << dt/1000000<< endl;
  cgr.getInputGlobalRoutingInfoInBox ( stream_file );
  cout << "EOF" <<  endl;
  exit(0);
  cgr.getInputGlobalRoutingInfo ( stream_file );

}

int runMode8 ( double stop_time, std::ofstream &stream_file ) 
{

  int num_ofl_edge = 0;
  for ( size_t i=0; i< cgr.E.size(); i++ )
    if ( cgr.E[i].cap!=0 && cgr.E[i].type!="VIA" && cgr.E[i].congestion_ratio > cgr.TCR )
      ++ num_ofl_edge;
  stream_file << "Number of bad edges = " << num_ofl_edge << endl;
  for  ( size_t rnd = 0; rnd < 4; rnd++ ) {

    stream_file << "ROUND " << rnd << " STARTS" << endl;
    //
    double  execution_time = 0;
    struct  timeval swap_start;
    gettimeofday ( &swap_start, NULL );
    //
    //  count the total number of the congested edges in whole layout
    cgr.countNumCongestedEdges ();

    int init_number_congested_edges = cgr.all_the_congested_edges.size();

    cout << "TOP20 = " << cgr.edge_CR.size() << endl;
    cout << "TOT EDGE = " << cgr.E.size() << endl;

    bool  debug_mode = false;
    string  delimiter ( 20, '#' );
    int status;

    //
    //  select a series of non-overlapping boxes
    vector<GridBox> boxes;
    for ( int i=0; i< cgr.edge_CR.size(); i++ ) {
      int edge_id = cgr.edge_CR[i].first;
      bool  isIncluded = false;
      for ( vector<GridBox>::iterator itr = boxes.begin(); itr!= boxes.end(); itr++ )
        if ( cgr.isInBox(cgr.E[edge_id].srcPoint, *itr) && cgr.isInBox(cgr.E[edge_id].snkPoint, *itr) ) {
          isIncluded = true;
          break;
        }
      if ( isIncluded==true )
        continue;
      GridBox b = cgr.buildBoxFrom3DCongestedEdge ( edge_id );
      if ( b.num_bad_edges < 10 )
        break;
      bool  isOverlapping = false;
      for ( vector<GridBox>::iterator itr = boxes.begin(); itr!= boxes.end(); itr++ )
        if ( cgr.isOverlappingBoxes ( *itr, b ) ) {
          isOverlapping = true;
          break;
        }
      if ( isOverlapping == true )
        continue;

      boxes.push_back ( b );
      b.printBox();
      if ( boxes.size()>=3 )
        break;
    }

    for ( size_t i=0; i< boxes.size(); i++ ) {
      boxes[i].printBox();
      cout << boxes[i].num_bad_edges << endl;
    }

    cout << boxes.size() << endl;

    for ( int i=0; i< boxes.size(); i++ ) {
      stream_file << "box[" << i << "]\t" << boxes[i].x0 << " " << boxes[i].y0 << " " <<boxes[i].dx << " " << boxes[i].dy << endl;
      fixOneBox3 ( boxes[i], stream_file );
      exit(0);
    }


    struct  timeval swap_end;
    gettimeofday ( &swap_end, NULL );
    double dt = (swap_end.tv_sec-swap_start.tv_sec)*1000000 + (swap_end.tv_usec-swap_start.tv_usec);
    stream_file << "runtime = " << dt/1000000<< endl;
    cout << "Check legality for all the " << cgr.bnets.size() << " modified nets in bounding box" << endl;
    cout << "###########################################################" << endl;
    //    cgr.getInputGlobalRoutingInfoInBox ( stream_file );
    stream_file << "runtime = " << dt/1000000<<endl; 
    cgr.getInputGlobalRoutingInfo ( stream_file );
    stream_file << "ROUND " << rnd << " ENDS" << endl;
  }

  return  1;
}
